class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<vector<int>> dp1(n + 1, vector<int>(3, 0));
        auto dp2 = dp1;
        auto dp3 = dp1;

        for (int i = 1; i < n + 1; i++)
        {
            dp1[i][0] = min(dp2[i - 1][1], dp3[i - 1][2]) + costs[i - 1][0];
            dp2[i][1] = min(dp1[i - 1][0], dp3[i - 1][2]) + costs[i - 1][1];
            dp3[i][2] = min(dp1[i - 1][0], dp2[i - 1][1]) + costs[i - 1][2];
        }

        return min(dp1[n][0], min(dp2[n][1], dp3[n][2]));
    }
};